#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "head.h"
// 数据类型
#define DATA_TYPE int

//创建一个空链表
p_linklist list_Create();
//尾插
int list_tail_insert(p_linklist H, DATA_TYPE value);//head
//获得指定位置的结点
int list_get(p_linklist H, int pos);//通过pos 获得第pos个位置的结点
//头插
int list_head_insert(p_linklist H, DATA_TYPE value);
//指定位置插入
int list_insert(p_linklist H, DATA_TYPE value, int pos);//将value插入到第pos结点之前
//销毁链表
p_linklist list_free(p_linklist *H);
//删除某一个位置上的结点
int list_delete(p_linklist H, int pos);
//修改结点数据
int list_Change(p_linklist H,DATA_TYPE value,DATA_TYPE newvalue);
// 遍历链表
int list_show(p_linklist H);

int main(int argc, char const *argv[])
{
    p_linklist HEAD=NULL;
    //指定位置插入测试
    HEAD=list_Create();
     //尾插
    printf("尾插测试:1 2 3\n");
    list_tail_insert(HEAD,1);
    list_tail_insert(HEAD,2);
    list_tail_insert(HEAD,3);
   //遍历
    list_show(HEAD);


    //头插
    printf("头插测试:4 5 6\n");
    list_head_insert(HEAD,4);
    list_head_insert(HEAD,5);
    list_head_insert(HEAD,6);
    //遍历
    list_show(HEAD);
    printf("\n");

    //翻转
    printf("翻转测试\n");
    list_reverse(HEAD);
    list_show(HEAD);

    //获得指定位置结点
    printf("获得指定位置结点测试\n");
    printf("获得第一个结点\n");
    list_get(HEAD, 1);
    printf("获得最后一个结点\n");
    list_get(HEAD, 6);
    printf("获得非法结点\n");
    list_get(HEAD, 7);
    printf("获得中间结点\n");
    list_get(HEAD, 3);

    //指定位置插入测试
    printf("\n");
    printf("指定位置插入数据,第1个位置\n");
    list_insert(HEAD,7,1);//在第一个位置插入
    list_show(HEAD);
    printf("指定位置插入数据,第4个位置\n");
    list_insert(HEAD,8,4);//在中间位置插入
    list_show(HEAD);
    printf("指定位置插入数据，非法位置\n");
    list_insert(HEAD,9,10);//在非法位置插入
    list_show(HEAD);
    printf("指定位置插入数据,第9个位置\n");
    list_insert(HEAD,10,9);//在最后一个位置插入
    list_show(HEAD);
  
    //修改测试
   printf("\n");
   list_Change(HEAD,6,66);
   list_show(HEAD);
   list_Change(HEAD,1,11);
   list_show(HEAD);
   list_Change(HEAD,10,1010);
   list_show(HEAD);
   list_Change(HEAD,7,77);
   list_show(HEAD);
   list_Change(HEAD,9,99);
   list_show(HEAD);

   //删除测试
   printf("\n");
   printf("删除指定位置的元素 测试\n");
   printf("指定位置删除数据,第1个位置\n");
   list_delete(HEAD,1);
   list_show(HEAD);
   printf("指定位置删除数据,最后一个位置\n");
   list_delete(HEAD,8);
   list_show(HEAD);
   printf("指定位置删除数据,第3个位置\n");
   list_delete(HEAD,3);
   list_show(HEAD);
   printf("指定位置删除数据,非法位置\n");
   list_delete(HEAD,9);
   list_show(HEAD);   
 
   //销毁
   printf("\n");
   printf("销毁测试\n");
   list_free(&HEAD);
   list_show(HEAD);

    
    //获得指定位置结点
    printf("获得指定位置结点测试\n");
    printf("获得第一个结点\n");
    list_get(HEAD, 1);
    printf("获得最后一个结点\n");
    list_get(HEAD, 6);
    printf("获得非法结点\n");
    list_get(HEAD, 7);
    printf("获得中间结点\n");
    list_get(HEAD, 3);

    //指定位置插入测试
    printf("\n");
    printf("指定位置插入数据,第1个位置\n");
    list_insert(HEAD,7,1);//在第一个位置插入
    list_show(HEAD);
    printf("指定位置插入数据,第4个位置\n");
    list_insert(HEAD,8,4);//在中间位置插入
    list_show(HEAD);
    printf("指定位置插入数据，非法位置\n");
    list_insert(HEAD,9,10);//在非法位置插入
    list_show(HEAD);
    printf("指定位置插入数据,第9个位置\n");
    list_insert(HEAD,10,9);//在最后一个位置插入
    list_show(HEAD);
  
    //修改测试
   printf("\n");
   list_Change(HEAD,6,66);
   list_show(HEAD);
   list_Change(HEAD,1,11);
   list_show(HEAD);
   list_Change(HEAD,10,1010);
   list_show(HEAD);
   list_Change(HEAD,7,77);
   list_show(HEAD);
   list_Change(HEAD,9,99);
   list_show(HEAD);

   //删除测试
   printf("\n");
   printf("删除指定位置的元素 测试\n");
   printf("指定位置删除数据,第1个位置\n");
   list_delete(HEAD,1);
   list_show(HEAD);
   printf("指定位置删除数据,最后一个位置\n");
   list_delete(HEAD,8);
   list_show(HEAD);
   printf("指定位置删除数据,第3个位置\n");
   list_delete(HEAD,3);
   list_show(HEAD);
   printf("指定位置删除数据,非法位置\n");
   list_delete(HEAD,9);
   list_show(HEAD);   
 
   //销毁
   printf("\n");
   printf("销毁测试\n");
   list_free(&HEAD);
   list_show(HEAD);

    return 0;
}

//创建一个空链表
p_linklist list_Create()
{
    p_linklist head;
    head=(p_linklist)malloc(sizeof(Lnode));
    //判断是否分配成功
    if(head==NULL)
    {
        printf("malloc failed\n");
    }
    //头结点不用来存储数据
    head->data=0;
    head->next=NULL;
    return head;
}

//尾插  失败：-1
int list_tail_insert(p_linklist H, DATA_TYPE value)
{
    //链表是否存在
    if(H==NULL)
    {
        printf("list is error\n");//链表不存在
        return -1;
    }
    //创建一个新结点
    p_linklist newnode=(p_linklist)malloc(sizeof(Lnode));
    if(newnode==NULL)
    {
        printf("newnode malloc faild\n");//新结点创建失败
        return -1;
    }
    //将新数据给新结点
    newnode->data=value;
    newnode->next=NULL;

    //找到尾结点
    p_linklist p_head=H;
    while (p_head->next!=NULL)
    {
        p_head=p_head->next;
    }
    //此时p_head指向尾结点
    p_head->next=newnode;
    return 0;
}

//获得指定位置的结点
int list_get(p_linklist H, int pos)//通过pos 获得第pos个位置的结点
{
    p_linklist p=H->next;
    int i=1;
    if(H==NULL)
    {
        printf("list is error\n");
        return -1;
    }
    if(pos<1)
    {
        printf("pos is error\n");
        return -1;
    }
    while(i<pos)
    {
      p=p->next;
      if(p==NULL)
      {
        printf("pos is large\n");
        return -1;
      }
      i++;
    }
    printf("指定位置%d的结点值为:%d",pos,p->data);
    return 0;
}

//头插
int list_head_insert(p_linklist H, DATA_TYPE value)
{
    //链表是否存在
    if(H==NULL)
    {
        printf("list is error\n");//链表不存在
        return -1;
    }
    p_linklist newnode=(p_linklist)malloc(sizeof(Lnode));
    if(newnode==NULL)
    {
        printf("newnode malloc faild\n");//新结点创建失败
        return -1;
    }
    //将新数据给新结点
    newnode->data=value;
    newnode->next=NULL;

    newnode->next=H->next;
    H->next=newnode;
    return 0;
} 
   

//指定位置插入
int list_insert(p_linklist H, DATA_TYPE value, int pos)//将value插入到第pos结点之前
{
     //链表是否存在
     if(H==NULL)
     {
         printf("list is error\n");//链表不存在
         return -1;
     }
     //pos位置要不要判断
     if(pos<1)
     {
        printf("pos is error\n");
        return -1;
     }
     //如果是第一个结点之前插入 就是头插
     if(pos==1)
     {
        list_head_insert(H,value);
        return 0;
     }
     //找pos位置
     p_linklist phead=H->next;
     int i=1;
     while(i<pos-1)
     {
        phead=phead->next;
        if(phead==NULL)
        {
            printf("pos is large\n");
            return -1;
        }
        i++;
     }
     //phead指向要插入结点的前一个位置
     //若待插入结点位置为空
     //尾插
     if(phead->next==NULL)
     {
        list_tail_insert(H,value);
        return 0;
     }

     //创建一个新结点
     p_linklist newnode=(p_linklist)malloc(sizeof(Lnode));
     if(newnode==NULL)
     {
         printf("newnode malloc faild\n");//新结点创建失败
         return -1;
     }
     //将新数据给新结点
     newnode->data=value;
     newnode->next=NULL;

     newnode->next=phead->next;
     phead->next=newnode;

     return 0;
}

//销毁链表
p_linklist list_free(p_linklist *H)
{
    //链表是否为空
    if(H==NULL)
    {
        printf("list is error\n");
        return NULL;
    }
    p_linklist phead=(*H)->next,temp;
    while (phead!=NULL)
    {
        //先存起来  phead
        temp=phead;
        phead=phead->next;
        memset(temp,0,sizeof(Lnode));
        free(temp);//释放
    }
    //释放头结点
    memset((*H),0,sizeof(Lnode));
    free(*H);
    *H=NULL;
   
    return NULL;

}

//删除某一个位置上的结点
int list_delete(p_linklist H, int pos)
{
    p_linklist temp;
    if(H==NULL)
    {
        printf("list is error\n");
        return -1;
    }
    if(pos<1)
    {
        printf("pos is error\n");
        return -1;
    }
   if(H->next==NULL)
   {
    printf("list is null\n");
    return -1;
   }
   if(pos==1)
   {
    temp=H->next;
    H->next=H->next->next;
    memset(temp,0,sizeof(Lnode));
    free(temp);
    return 0;
   }
   //找pos的位置
   p_linklist phead=H->next;
   int i=1;
   while(i<pos-1)
   {
      phead=phead->next;
      if(phead==NULL)
      {
        printf("pos is large\n");
        return -1;
      }
      i++;
   }
   if(phead->next==NULL)
   {
    printf("delete error\n");
    return -1;
   }

   //进行结点删除
   temp=phead->next;
   phead->next=temp->next;
   memset(temp,0,sizeof(Lnode));
   free(temp);
   return 0;
}

//修改结点数据
int list_Change(p_linklist H,DATA_TYPE value,DATA_TYPE newvalue)
{   
    p_linklist p=H->next;

    if(H==NULL)
    {
        printf("list is error\n");
        return -1;
    }

    while(p->data!=value)
    {
      p=p->next;
      if(p==NULL)
      {
        printf("not find value\n");
        return -1;
      }
      else
      {
        p->data=newvalue;
        return 0;
      }
    }
    return 0;
    
}

// 遍历链表
int list_show(p_linklist H)
{
    //判空 判断链表是否存在
    if(H==NULL)
    {
        printf("list is error\n");
        return -1;
    }
    //因为是带头结点的单链表
    if(H->next==NULL)
    {
        printf("list is empty\n");
        return -1;
    }
    printf("遍历\n");
    //遍历
    p_linklist phead=H->next;//可以从下一个结点开始遍历
    while(phead)
    {
        printf("%d \t",phead->data);
        phead=phead->next;
    }
    printf("\n");
    return 0;

}

//链表的翻转/转置
int list_reverse(p_linklist H)
{
    //判空 判断链表是否存在
    if(H==NULL)
    {
        printf("list is error\n");
        return -1;
    }
    if(H->next==NULL)
    {
        printf("list is empty\n");
        return -1;
    }
    //只有一个结点 不需要翻转
    if(H->next->next==NULL)
    {
        return 0;
    }
    p_linklist phead=H->next,qhead=H->next->next;
    phead->next=NULL;
    while(qhead!=NULL)
    {
        phead=qhead;
        qhead=qhead->next;
        phead->next=H->next;
        H->next=phead;
    }
    return 0;
}